package airthmetic.exercise.tree;

/**
 * @Author douhy
 * @description 完全二叉树练习
 * @date 22/01/14
 */
public class CompleteBinaryTree {


    // 如果一棵完全二叉树有 768 个节点，求叶子节点的个数
    public static Integer getLeafNodeNumber(){
        // 思路
        // n0 = 叶子结点 n1 = 度为1的节点 n2 = 度为2的节点
        // 完全二叉树 度为1的节点为 0 或 1个
        // 全部节点为 n = n0 + n1 + n2
        // 又有公式 n0 = n2 + 1
            // 对于任何一颗非空二叉树，如果叶子节点个数为n0,度为2的节点个数为n2,则有 n0 = n2 + 1
            // 假设 全部节点为 n = n0 + n1 + n2
            // 二叉树的边数 T = n1 + 2 * n2 = n - 1 = n0 + n1 + n2 - 1
            // 因此 n0 = n2 + 1
        // 故 n = 2no + n1 -1

        // n1 = 1
        // n = 2n0 + 1 - 1 = 2n0 = n0 = floor(n / 2) = ceiling((n-1) / 2)

        // n1 =0
        // n = 2n0 + 0 - 1 = 2n0 - 1 =  n0 = floor((n + 1) / 2) = ceiling( n / 2)

        return (int) Math.ceil(768 / 2);
    }
    public static void main(String[] args) {
        System.out.println(getLeafNodeNumber());
    }

}
